package tree.递归;

import po.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N二叉搜索树中第K小的元素230.java
 * @Description TODO https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/
 * @createTime 2021年04月15日 13:05:00
 */
public class N二叉搜索树中第K小的元素230 {

    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> deque=new LinkedList<>();
        while (true) {
            //一直遍历左子树的左子节点
            while (root != null) {
                deque.offerLast(root);
                root=root.left;
            }
            TreeNode node = deque.pollLast();
            k-=1;
            if (k==0){
                return node.val;
            }
            //数量没有到k个，就继续最后一个左子树的右子树
            if (node.right!=null){
                root=node.right;
            }
        }
    }
}
